Bernstein-Vazirani Algorithm
Quantum Solution

1. Initial

• inputs qubits to |0⟩⊗n
• output qubit to |−⟩

2. Apply Hadamard gates to input register
3. Query
4. Apply Hadamard gates to input register
5. Measure

Simon's Algorithm
Simon's Problem

• Given an unknown function f, which is guaranteed to be either one-to-one or two-to-one
• • one-to-one - Maps exactly one unique output for every input
• • two-to-one - Maps exactly two inputs to every unique output
• Classical Solution
• • Have to check up to (2^(n−1))+1 inputs